\section{Kolorowanie wierzchołków}
  Aby pokolorować wierzchołki poprawnie według klasycznego modelu wierzchołki incydentne muszą otrzymać różne barwy a więc każda krawędź musi łączyć wierzchołki różnych wartości. Inaczej też można powiedzieć że dzielimy zbiór $V$ wierzchołkow na rozdzielne podzbiory, w których nie istnieją połączenia między elementami jednego podzbioru czyli wyznaczamy k, dla którego graf jest k-dzielny.

  \begin{Def}
	Graf nazywamy \textit{k-kolorowalnym} (k-barwnym) jeśli istnieje dla niego poprawne kolorowanie używające k kolorów (k-pokolorowanie).
  \end{Def}

  \begin{Def}
	Najmniejszą liczbę k, dla której graf $G$ jest k-kolorowalny wierzchołkowo nazywamy jego \textit{liczbą chromatyczną}, co oznaczamy przez $\chi(G)$. Każde $\chi(G)$-pokolorowanie grafu będziemy nazywać chromatycznym.
  \end{Def}

  \begin{Def}
	\textit{Stopniem nasycenia} lub \textit{stopniem saturacyjnym} $\rho(v)$ wierzchołka $v$ będziemy nazywać (w grafie częściowo pokolorowanym) liczbę kolorów użytych przy kolorowaniu wierzchołków z nim incydentnych.
  \end{Def}

  \subsection{Twierdzenia ogólne}\label{classicmodel:general}
	\begin{Tw}\label{classicmodel:general:delplus1}
	  Graf prosty, w ktorym największy stopień wierzchołka wynosi $\Delta$ jest \newline $(\Delta+1)-kolorowalny$.
	\end{Tw}
	\begin{Dw}
	  Udowodnić to można przez indukcję względem liczby wierzchołków. Usuwając wierzchołek (razem z krawędziami incydentnymi z nim) stopnia $\Delta$ na pewno nie zwiększymy liczby kolorów potrzebnych do pokolorowania grafu i maksymalny stopień wierzchołka dalej będzie niewiększy niż $\Delta$. Jeśli nawet wszystkie wierzchołki połączone wcześniej z tym, który usunęliśmy, są różnych kolorów, to jest ich najwyżej $\Delta$, więc dodając wierzchołek z powrotem pozostaje nam jeszce jedna barwa do wykorzystania. 
	\end{Dw}

	Nieco silniejszym jest twierdzenie Brooks'a:
	\begin{Tw}[Brooks'a]\label{classicmodel:general:twbrooks}
	  Każdy niepełny, spójny graf prosty o maksymalnym stopniu wierzchołka $\Delta \geq 3$ jest $\Delta$-kolorowalny. 
	  Grafy pełne oraz cykle o nieparzystej długości są $(\Delta + 1) $-kolorowalne.
	\end{Tw}
	\begin{Dw} 
	  Rozpatrzmy najpierw grafy niepełne nie będące cyklami, poprowadzimy dla nich dowód przez indukcję względem liczby wierzchołków rozpatrując kilka przypadków. W grafach o $|V|\le3$ sytuacja jest oczywista. Rozważmy wiec przypadek kiedy $|V|>3$. Jeśli graf ten zawiera wierzchołek $v$, którego usunięcie spowoduje rozspójnienie grafu można wtedy pokolorować osobno każdą składową spójną (o ilości wierzchołków $<|V|$) z dołączonym $v$ pamiętając jedynie o tym aby w każdej z nich wierzchołek $v$ miał jednakowy kolor.
	  \begin{figure}[!h]\centering\begin{tikzpicture}
		  \tikzstyle{every edge}=[draw=lightgray]
		  \tikzstyle{every node}=[draw=lightgray, circle, inner sep=0, minimum size=5pt]
		  \tikzstyle{ghost}=[draw=white]

		  \node(v11) at(30:1) {};
		  \node(v12) at(45:1) {};
		  \node(v13) at(15:1) {};

		  \node(v21) at(150:1) {};
		  \node(v22) at(165:1) {};
		  \node(v23) at(135:1) {};

		  \node(v31) at(270:1) {};
		  \node(v32) at(285:1) {};
		  \node(v33) at(255:1) {};

		  \node(w)[label=$v$, black] at(0,0) {}
			  edge(v11) edge(v12) edge(v13)
			  edge(v21) edge(v22) edge(v23)
			  edge(v31) edge(v32) edge(v33);
		  
		  \pgftransformrotate{30}
		  \draw(0:0.55)[dashed, lightgray] ellipse (0.7 and 0.5);
		  \pgftransformrotate{120}
		  \draw(0:0.55)[dotted] ellipse (0.7 and 0.5);
		  \pgftransformrotate{120}
		  \draw(0:0.55)[gray, densely dotted] ellipse (0.7 and 0.5);
	  \end{tikzpicture}\caption{}\end{figure}

	  W~\mbox{sytuacji} gdy takiego wierzchołka nie ma, wykorzystamy fakt, że w rozpatrywanych grafach musi istnieć trójka wierzchołków -- oznaczmy je przez $u,v$ i $w$ -- dla których $uw,vw \in E$, $uv \not\in E$, takie że usunięcie wierzchołków $u$ i $v$ nie rozspójnia grafu (dowód w \cite{aspektykombinatoryki} na stronie 256). Podgraf otrzymany przez usunięcie $u$ i $v$ oznaczmy przez $G'$.

	  Stwórzmy teraz ciąg wierzchołków: $v_1=u, v_2=v, v_n=w$ zaś pozostale wierzchołki ułużmy w $v_3,\ldots,v_{n-1}$, w kolejności odwrotnej do ich odległości od $w$ w grafie $G'$. Możemy teraz zauważyć, że każdy $v_i$ gdzie $1 \le i <n$ jest na pewno połączony z co najmniej jedym wierzchołkiem o większym indeksie. Kolorując następnie wierzchołki zgodnie z ich ułożeniem w tym ciągu nadajemy im kolory o najmniejszych indeksach nie użytych do tej pory przy kolorowaniu ich sąsiadów. Stopień saturacyjny nigdy nie przekroczy $\Delta$, ponieważ dla $v_1,v_{n-1}$ ich stopień jest niewiększy niż $\Delta$ oraz jest zawsze jeszcze wierzchołek o większym indeksie, czyli nie pokolorowany. Dla ostatniego wierzchołka $v_n=w$ także mamy wolny kolor ponieważ $v_1=v,v_2=u$ nie są ze sobą połączone i mają tę samą barwę$=1$ jako że były kolorowane na samym początku.
 
	  W grafach pełnych $K_n$ sprawa jest bardzo prosta, ponieważ każdy wierzchołek jest stopnia $\Delta=n-1$ a skoro wszystkie wierzchołki są połączone, to potrzebujemy $n=\Delta+1$ kolorów.

	  Cykle nieparzystej długości także nie są trudnym przypadkiem, bo każdy wierzchołek ma tam stopień $\Delta=2$. Kolorując wierzchołki kolejno dwoma kolorami na przemian, potrzebować będziemy na końcu dodatkowego koloru ponieważ inaczej pierwszy i ostatni otrzymałyby ten sam kolor.
	\end{Dw}

	Ciekawsze obserwacje można przeprowadzić na grafach planarnych, jako że mają pewne specjalne własności.

  \subsection{Twierdzenia o grafach planarnych}\label{classicmodel:planar}
	Na początek przedstawimy dwa twierdzenia o grafach, na których opierają się dalsze twierdzenia o kolorowaniu. Ich dowody pominiemy aby zachować jednolitość tematu pracy.
	\begin{Tw}\label{classicmodel:planar:twst5}
	  W każdym grafie planarnym istnieje wierzchołek o stopniu mniejszym lub rownym 5.
	\end{Tw}

	\begin{Tw}[Kuratowskiego]\label{classicmodel:planar:kuratowski}
	Graf jest planarny $\Leftrightarrow$ nie zawiera podgrafu izomorficznego z $K_5$ lub $K_{3,3}$.
	\end{Tw}
	Dowód pierwszego twierdzenia znaleźć można w książce \cite{wprowadzeniedoteorii}, szkic drugiego zaś w \cite{aspektykombinatoryki}.
	\newline

	Możemy teraz przejść do głównego tematu. Na początek, proste do udowodnienia twierdzenie:
	\begin{Tw}\label{classicmodel:planar:tw6barw}
	  Każdy graf planarny jest 6-kolorowalny
	\end{Tw}
	\begin{Dw}
	  Twierdzenie to udowodnimy przed indukcję względem liczby wierzchołków, będzie to bardzo podobny dowód do \ref{classicmodel:general:delplus1}. Dla grafów o najwyżej 6 wierzchołkach jest to oczywiste. Przy $|V| > 6$ zakładamy że każdy graf o mniejszej ilości wierzchołków jest 6-kolorowalny i skorzystamy z twierdzenia \ref{classicmodel:planar:twst5}. Tak więc bierzemy wierzchołek stopnia 5 (lub mniejszym jeśli taki nie istnieje) i usuwamy go z grafu (jak zwykle ze wszystkimi krawędziami incydentnymi). Oczywiste jest że redukując zbiór wierzchołków grafu nie zwiększymy jego liczby chromatycznej więc w założeniu indukcyjnym taki graf bedzie także 6-kolorowalny. Dodając usunięty wierzchołek z powrotem mamy dla niego na pewno co najmniej jedną dostępną barwę ponieważ sąsiadów jest co najwyżej pięciu (i nawet niekoniecznie muszą być różnych kolorów).
	\end{Dw}

	Przeprowadzając pewne obserwacje powyższego dowodu oraz wprowadzając do niego pewnie sztuczki można udowodnić silniejsze twierdzenie o 5 barwach.
	\begin{Tw}[P.J. Heawood]\label{classicmodel:planar:tw5barw}
	Każdy graf planarny jest 5-kolorowalny
	\end{Tw}
	\begin{Dw} 
	  Podobnie jak wyżej wykorzystamy indukcję względem ilości wierzchołków oraz twierdzenie o istnieniu wierzchołka stopnia $\deg(v) \leq 5$ (tw. \ref{classicmodel:planar:twst5}), a także fakt że grafy planarne nie zawierają kliki $K_5$ (tw. \ref{classicmodel:planar:kuratowski}). Znowu dla grafów o $|V| \le 5$ mamy banalną sytuację. Dla większych grafów, tak jak wcześniej, będziemy szukać barwy dla wierzchołka o ${\rm deg}(v)=5$ zakładając, że  grafy o mniejszej liczbie wierzchołków są 5-kolorowalne. Tak więc usuwamy wierzchołek $v$ z grafu i rozpatrujemy jego sąsiadów $v_1,\ldots,v_5$. Jeżeli są wśród nich wierzchołki o tych samych barwach, to mamy wolny kolor dla $v$. W przeciwnym wypadku musimy jakiś zwolnić. Jako że wiemy, iż w grafie planarnym nie może znajdować sie pełny podgraf $K_5$, to isnieje w zbiorze ${v_1,\ldots,v_5}$ para wierzchołków nie połączonych ze sobą, przypuśćmy że są to $v_2$ i $v_5$. \newline
	  \begin{figure}[!h]\centering\begin{tikzpicture}[scale=1.3]
		  \tikzstyle{every node}=[draw, inner sep=0, minimum size=5, circle]
		  \tikzstyle{nonv}=[lightgray]
				
		  \node(v)[label=60:$v$] at(0,0) {};
			  \foreach \i in {1,2,3,4,5}
				  \node(v\i)[label=18+\i*72:$v_\i$] at(18+\i*72:1) {} edge(v);

		  \node(g21)[nonv] at(120:2) {} edge(v2)[nonv];
		  \node(g22)[nonv] at(180:2) {} edge(v2)[nonv];
		  \node(g51)[nonv] at(60:2) {} edge(v5)[nonv];
		  \node(g52)[nonv] at(0:2) {} edge(v5)[nonv];
		  
		  \begin{scope}[xshift=6cm]
			  \node(v)[label=270:$v$] at(0,0) {};
			  \foreach \i in {1,3,4}
				  \node(v\i)[label=18+\i*72:$v_\i$] at(18+\i*72:1) {} edge(v);

			  \node(g21)[nonv] at(120:2) {} edge(v)[nonv];
			  \node(g22)[nonv] at(180:2) {} edge(v)[nonv];
			  \node(g51)[nonv] at(60:2) {} edge(v)[nonv];
			  \node(g52)[nonv] at(0:2) {} edge(v)[nonv];
		  \end{scope}

		  \draw[stealth-stealth, snake=snake, line before snake=1mm, line after snake=1mm, segment amplitude=0.4mm, segment length=2mm, gray] (2.2,0) -- (3.8, 0);
	  \end{tikzpicture}\caption{}\end{figure}

	  Ściągając teraz krawędzie $vv_2$ oraz $vv_5$ znowu tworzymy graf o mniejszej ilości wierzchołków a więc -- według założeń indukcji -- 5-kolorowalny. Biorąc z tego grafu kolor wierzchołka $v$, można nadać go wierzchołkom $v_2$ i $v_5$ w poprzednim rozważanym grafie. W rezultacie mamy użyte jedynie 4 kolory wśród sąsiadów $v$, a więc jeszcze jeden jest wolny.
	\end{Dw}

	Ostatecznie przedstawimy twierdzenie które przez długie lata, mimo wielu prób pozostawało nie udowodnione przez żadnego matematyka, dzięki czemu zyskało status jednego z najsłynniejszych problemów matematycznych. Postawienie tezy tego twierdzenia zapoczątkowało w zasadzie prace nad zagadnieniem kolorowania grafów, a nawet całej teorii grafów.
	\begin{Tw}[o czterech barwach]\label{classicmodel:planar:tw4barw}
	  Każdy graf planarny jest 4-kolorowalny.
	\end{Tw}
	Twierdzenie jak już zostało wspomniane we wstępie było początkowo udowodnione nieprawidłowo. Po dostrzeżeniu w nim blędu nie potrafiono znaleźc poprawnego dowodu do XX~w. kiedy to można było użyć komputerów do sprawdzania ogromnej ilości kombinacji grafowych co człowiekowi zajęło by dużo więcej czasu. Wszyskie znane dotąd dowody tego twierdzenia są bardzo długie co uniemożliwia umieszczenie ich w tej pracy, poza tym wszystkie nadal używają dużej ilości obliczeń komputerowych.

  \subsection[Zastosowania]{Zastosowania kolorowania wierzchołków}
	Kolorowanie wierzchołków wykorzystujemy gdy mamy problem polegający na rozdzieleniu pewnych rzeczy (wierzchołków) między którymi występują konflikty (krawędzie). Rozważmy kilka przykładów:\newpage
	\begin{Prz}
	  Pewien chemik ma w swoim laboratorium różne substancje, z których pewne mogą ze sobą reagować. Może rozdzielać poszczególne chemikalia od siebie, jednak chciał aby podział był jak najmniejszy (nie umieszczać wszystkiego gdzie indziej).

	  Możemy tutaj skojarzyć chemikalia z wierzchołkami grafu a nieporządane reakcje z krawędziami, tworzymy w ten sposób graf i kolorujemy go optymalnie. W ten sposób otrzymujemy podział -- substancje (wierzchołki) jednakowych kolorów można umieścić w jednym miejscu ponieważ nie będą ze sobą reagować
	\end{Prz}
	Innym przykładem może być ustalanie rozkładu zajęć.
	\begin{Prz} % TODO do przemyślenia...
	  Na uczelni należy przygotować rozkład zajęć i wiadomo że niektórzy studenci muszą uczęszczać na kilka wykładów. Oczywiście zajęcia powinny mieścić się w jak najmniejszym przedziale czasowym. Tak więc wykłady stają sie wierzchołkami a kolizje między nimi krawędziami. Po kolorowaniu takiego grafu zajęcia z jednakowym kolorem mogą odbywać się w tym samym czasie.
	\end{Prz}

	\begin{Prz}\label{example:gasstations}
	  W mieście znajduje się kilka skrzyżowań połączonych ze sobą drogami (niekoniecznie bezpośrednio). Pewne koncerny chcą wybudować przy tych skrzyżowaniach stacje benzynowe. Na każdym skrzyżowaniu może znajdować sie jedynie jedna stacja, a poza tym żaden koncern nie chce mieć dwóch stacji na sąsiednich skrzyżowaniach ze względów ekonomicznych. Aby dojść do porozumienia muszą ustalić kolorowanie grafu przedstawiającego interesujące ich skrzyżowania używające dokładnie tylu kolorów ile koncernów uczestniczy w tym układzie. Przypuśćmy że graf będzie wyglądał jak przedstawiono poniżej a w porozumieniu uczestniczą 4 koncerny: $A,B,C,D$\newline
	  \begin{figure}[!h]\centering\begin{tikzpicture}[scale=1.6]
		\tikzstyle{every node}=[draw, circle, inner sep=0, minimum size=5]
		\foreach \i/\l in {1/$a$,2/$b$,3/$c$,4/$d$}
			\node(v\i)[label={(\i*90-45)}:\l] at({(\i*90-45)}:1) {}
				\foreach \j in {1,...,\i} {
					edge(v\j)
				};
		\node(v5)[label=0:$b$ lub $c$] at(1.5,0) {}
		  edge(v1) edge(v4);
	  \end{tikzpicture}\caption{}\end{figure}
	  \newpage Mamy tutaj przykładowe kolorowanie takiego grafu. Jeżeli teraz którykolwiek z uczestników umowy wycofałby się, to cały układ nie doszedłby do skutku, ponieważ grafu tego nie da się pokolorować mniejszą ilością kolorów. Koncernom pozostaje jeszcze ustalenie do kogo należą stacje oznaczone konkretnym kolorem (jako że podział nie jest równy), ale nie jest to już problem, jaki rozważamy w tej pracy.
	\end{Prz}
	
	\begin{Prz}\label{example:sudoku}
	  Rozwiązywanie popularnej ostatnimi czasy łamigłówki ``Sudoku'' jest także niczym innym jak kolorowaniem specyficznego grafu, który jest już częściowo pokolorowany. Gdy każda kratka reprezentowana będzie przez osobny wierzchołek, będzie on połączony ze wszystkimi wierzchołkami z tego samego wiersza, kolumny oraz 'podkwadratu', w którym się znajduje. Kolory są tu po prostu liczbami naturalnymi od 1 do 9, a pokolorowanie rozwiązaniem.
	\end{Prz}

